﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Problems.Sorting;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Geometry.ClosestPair
{
    public class ClosestPointsFinder1 : IClosestPointsFinder
    {
        private IList<Point2D> _sortedPoints;
        private readonly ISorter<Point2D> _sorter;


        public ClosestPointsFinder1(Func<ISorter<Point2D>> createSorter = null)
        {
             createSorter = createSorter ?? (() => new BasicQuickSorter<Point2D>());
            _sorter = createSorter();
        }

        private double MinimumDistance(int a, int b)
        {
            if ( b - a < 2)
            {
                return double.PositiveInfinity;
            }
            if ( b -a == 2)
            {
                return Utils.EuclideanDistance(_sortedPoints[a], _sortedPoints[a + 1]);
            }
            int c = (a + b)/2;
            var leftMinDistance = MinimumDistance(a, c);
            var rightMinDistance = MinimumDistance(c, b);
            var distance = (from i in Enumerable.Range(a,c-a)
                            from j in Enumerable.Range(c,b-c)
                            select Utils.EuclideanDistance(_sortedPoints[i],_sortedPoints[j])).Min();
            return new[] {leftMinDistance, rightMinDistance, distance}.Min();
        }

        private Tuple<Point2D,Point2D> MinimumClosestPoints(int a, int b, out double d)
        {
            if ( b -a  < 2)
            {
                d = double.PositiveInfinity;
                return new Tuple<Point2D, Point2D>(null, null);
            }
            if ( b - a == 2)
            {
                d = Utils.EuclideanDistance(_sortedPoints[a], _sortedPoints[a + 1]);
                return new Tuple<Point2D, Point2D>(_sortedPoints[a],_sortedPoints[a+1]);
            }
            int c = (a + b)/2;
            double leftDist, rightDist;
            var left = MinimumClosestPoints(a, c, out leftDist);
            var right = MinimumClosestPoints(c, b, out rightDist);
            var candidate = right;
            d = rightDist;
            if ( leftDist < rightDist)
            {
                candidate = left;
                d = leftDist;
            }

            var current = (from i in Enumerable.Range(a, c - a)
                           from j in Enumerable.Range(c, b - c)
                           select
                               new Tuple<double, Point2D, Point2D>(
                               Utils.EuclideanDistance(_sortedPoints[i], _sortedPoints[i + 1]),
                               _sortedPoints[i], _sortedPoints[i + 1])).ArgMin(t1 => t1.Item1);

            if ( d < current.Item1)
            {
                return candidate;
            }
            else
            {
                return new Tuple<Point2D, Point2D>(current.Item2,current.Item3);
            }
        }

        #region Implementation of IClosestPointsFinder<T>

        public double DistanceBetweenClosestPoints(IList<Point2D> points)
        {
            _sortedPoints = _sorter.Sorted(points).ToAlgoritmiaList();
            return MinimumDistance(0, points.Count);
        }

        public Tuple<Point2D, Point2D> ClosestPoints(IList<Point2D> points)
        {
            _sortedPoints = _sorter.Sorted(points).ToAlgoritmiaList();
            double g;
            return MinimumClosestPoints(0, points.Count, out g);
        }

        #endregion
    }

    public class ClosestPointsFinder : IClosestPointsFinder
    {
        private IList<Point2D> _points;
        private readonly ISorter<int> _sorter;

        public ClosestPointsFinder(Func<ISorter<int>> createSorter = null)
        {
            createSorter = createSorter ?? (() => new BasicQuickSorter<int>());
            _sorter = createSorter();

        } 

        private double MinimumDistance(IList<int> x, IList<int> y)
        {
            if ( x.Count <= 1)
            {
                return double.PositiveInfinity;
            }
            if ( x.Count == 2)
            {
                return Utils.EuclideanDistance(_points[x[0]], _points[x[1]]);
            }

            var splitter = (_points[x[x.Count/2 - 1]].X + _points[x[x.Count/2]].X)/2.0;
            var x1 = (from i in x
                     where _points[i].X <= splitter
                     select i).ToAlgoritmiaList();
            var x2 = (from i in x
                      where _points[i].X > splitter
                      select i).ToAlgoritmiaList();
            var y1 = (from i in y
                      where _points[i].Y <= splitter
                      select i).ToAlgoritmiaList();
            var y2 = (from i in y
                      where _points[i].Y > splitter
                      select i).ToAlgoritmiaList();
            var delta1 = MinimumDistance(x1, y1);
            var delta2 = MinimumDistance(x2, y2);
            double delta = Math.Min(delta1, delta2);
            var strip = (from i in y where Math.Abs(_points[y[i]].X - splitter) < delta select i).ToAlgoritmiaList();

            for (int i = 0; i < strip.Count; i++)
            {
                for (int j = i + 1; j < strip.Count; j++)
                {
                    if (Math.Abs(_points[strip[i]].Y - _points[strip[j]].Y) > delta)
                    {
                        break;
                    }
                    delta = Math.Min(delta, Utils.EuclideanDistance(_points[strip[i]], _points[strip[j]]));
                }
            }

            return delta;
        }

        private Tuple<Point2D,Point2D> ClosestPair(IList<int> x, IList<int> y, out double delta)
        {
            if (x.Count <= 1)
            {
                delta = double.PositiveInfinity;
                return new Tuple<Point2D, Point2D>(null,null);
            }
            if (x.Count == 2)
            {
                delta = Utils.EuclideanDistance(_points[x[0]], _points[x[1]]);
                return new Tuple<Point2D, Point2D>(_points[x[0]], _points[x[1]]);
            }

            var splitter = (_points[x[x.Count / 2 - 1]].X + _points[x[x.Count / 2]].X) / 2.0;
            var x1 = (from i in x
                      where _points[i].X <= splitter
                      select i).ToAlgoritmiaList();
            var x2 = (from i in x
                      where _points[i].X > splitter
                      select i).ToAlgoritmiaList();
            var y1 = (from i in y
                      where _points[i].Y <= splitter
                      select i).ToAlgoritmiaList();
            var y2 = (from i in y
                      where _points[i].Y > splitter
                      select i).ToAlgoritmiaList();
            double delta1, delta2;
            var lessSplitter = ClosestPair(x1, y1, out delta1);
            var greaterSplitter = ClosestPair(x2, y2, out delta2);
            var tempSolution = greaterSplitter;
            delta = delta2;
            
            if ( delta1 < delta2)
            {
                delta = delta1;
                tempSolution = lessSplitter;
            }
            double d = delta;
            var strip = (from i in y where Math.Abs(_points[y[i]].X - splitter) < d select i).ToAlgoritmiaList();

            for (int i = 0; i < strip.Count; i++)
            {
                for (int j = i + 1; j < strip.Count; j++)
                {
                    if (Math.Abs(_points[strip[i]].Y - _points[strip[j]].Y) > delta)
                    {
                        break;
                    }
                    d = Utils.EuclideanDistance(_points[strip[i]], _points[strip[j]]);
                    if ( delta > d )
                    {
                        delta = d;
                        tempSolution = new Tuple<Point2D, Point2D>(_points[strip[i]],_points[strip[j]]);
                    }
                }
            }
            return tempSolution;
        }

        #region Implementation of IClosestPointsFinder<double>

        public double DistanceBetweenClosestPoints(IList<Point2D> points)
        {
            _points = points;
            var x = _sorter.Sorted(Enumerable.Range(0,points.Count).ToAlgoritmiaList(), (a, b) => _points[a].X.CompareTo(_points[b].X)).ToAlgoritmiaList();
            var y = _sorter.Sorted(Enumerable.Range(0, points.Count).ToAlgoritmiaList(), (a,b) => _points[a].Y.CompareTo(_points[b].Y)).ToAlgoritmiaList();
            return MinimumDistance(x, y);
        }

        public Tuple<Point2D, Point2D> ClosestPoints(IList<Point2D> points)
        {
            _points = points;
            var x = _sorter.Sorted(Enumerable.Range(0, points.Count).ToAlgoritmiaList(), (a, b) => _points[a].X.CompareTo(_points[b].X)).ToAlgoritmiaList();
            var y = _sorter.Sorted(Enumerable.Range(0, points.Count).ToAlgoritmiaList(), (a, b) => _points[a].Y.CompareTo(_points[b].Y)).ToAlgoritmiaList();
            double delta;
            return ClosestPair(x, y, out delta);
        }

        #endregion
    }
}
